package 二叉树;
import java.util.*;
/**
 * 二叉树的层序遍历
 * 从上到下按层遍历二叉树，每一层从左到右访问所有节点
 * 时间复杂度O(n)，空间复杂度O(n)，n为节点个数
 */
public class levelOrder {
    /**
     * 二叉树节点类
     * 包含节点值、左子节点和右子节点
     */
    public static class TreeNode{
        int val;            // 节点值
        TreeNode left;      // 左子节点
        TreeNode right;     // 右子节点
        
        // 无参构造函数
        TreeNode(){}
        
        // 带值的构造函数
        TreeNode(int val){
            this.val = val;
        }
        
        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 层序遍历二叉树的方法
     * 使用队列实现，每次处理一层
     * 
     * @param root 二叉树的根节点
     * @return 层序遍历结果，每一层的结果存储在一个List中
     */
    public static List<List<Integer>> levelOrderM(TreeNode root){
        // 存储最终结果的列表
        List<List<Integer>> res = new ArrayList<>();
        // 处理空树的情况
        if(root == null) return res;

        // 双端队列（Deque）既可以当作队列使用，也可以当作栈使用：
        // 1. 队列用法（先进先出）：offer() 从队尾加入，poll() 从队首取出
        //    例：deque.offer(1); deque.offer(2); int x = deque.poll(); // x=1
        // 2. 栈用法（后进先出）：push() 从队首加入，pop() 从队首取出
        //    例：deque.push(1); deque.push(2); int x = deque.pop(); // x=2
        // 在本题中，主要用作队列，按层遍历二叉树
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);  // 将根节点加入队列
        
        // 当队列不为空时，继续处理
        while(!deque.isEmpty()){
            int size = deque.size();  // 当前层的节点数
            ArrayList<Integer> level = new ArrayList<>();  // 存储当前层的节点值
            
            // 处理当前层的所有节点
            for(int i = 0; i < size; i++){
                TreeNode node = deque.poll();  // 取出队首节点
                // 将左右子节点加入队列
                if(node.left != null) deque.offer(node.left);
                if(node.right != null) deque.offer(node.right);
                level.add(node.val);  // 将当前节点值加入当前层的结果列表
            }
            res.add(level);  // 将当前层的结果加入最终结果
        }
        return res;
    }

    /**
     * 根据层序遍历的字符串数组构建二叉树
     * 使用队列进行层序遍历构建
     * 
     * @param nodes 层序遍历的节点值数组，"null"表示空节点
     * @return 构建好的二叉树根节点
     */
    public static TreeNode buildTree(String[] nodes){
        // 处理特殊情况：空数组或根节点为空
        if(nodes.length == 0 || nodes[0].equals("null") || nodes == null){
            return null;
        }

        // 使用队列进行层序遍历构建
        Queue<TreeNode> queue = new LinkedList<>();
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        
        int index = 1;  // 当前处理的节点在数组中的索引
        // 层序遍历构建二叉树
        while(!queue.isEmpty() && index < nodes.length){  // 外层循环已经保证了index < nodes.length
            TreeNode cur = queue.poll();  // 取出当前节点
            
            // 处理左子节点，由于外层while已经保证了index < nodes.length，这里不需要重复判断
            // 不能使用 nodes[index] != null：
            //    这种写法只判断数组元素是否为 null（即引用为 null），
            //    但实际输入的 "null" 是字符串内容，不是 null 引用。
            //    例如：nodes[index] 的值为 "null"（字符串），此时 nodes[index] != null 为 true，
            //    但我们实际需要判断的是内容是否为 "null"。
            // 不能使用 nodes[index] != "null"：
            //    这种写法比较的是两个字符串对象的引用地址（内存地址），
            //    只有当它们指向同一个字符串常量池对象时才为 true，
            //    但实际输入时，字符串内容相同但引用不同的情况很常见，
            //    这样会导致判断失效，出现漏判或误判。
            // 正确做法是使用 equals 方法比较字符串内容：
            //    nodes[index].equals("null") 能准确判断内容是否为 "null" 字符串。
            if(!nodes[index].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.left);
            }
            index++;

            // 处理右子节点，由于外层while已经保证了index < nodes.length，这里不需要重复判断
            // 不能使用 nodes[index] != null：
            //    这种写法只判断数组元素是否为 null（即引用为 null），
            //    但实际输入的 "null" 是字符串内容，不是 null 引用。
            //    例如：nodes[index] 的值为 "null"（字符串），此时 nodes[index] != null 为 true，
            //    但我们实际需要判断的是内容是否为 "null"。
            // 不能使用 nodes[index] != "null"：
            //    这种写法比较的是两个字符串对象的引用地址（内存地址），
            //    只有当它们指向同一个字符串常量池对象时才为 true，
            //    但实际输入时，字符串内容相同但引用不同的情况很常见，
            //    这样会导致判断失效，出现漏判或误判。
            // 正确做法是使用 equals 方法比较字符串内容：
            //    nodes[index].equals("null") 能准确判断内容是否为 "null" 字符串。
            if(!nodes[index].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.right);
            }
            index++;
        }
        return root;
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用空格分隔，表示二叉树的层序遍历，"null"表示空节点
     * 例如：3 9 20 null null 15 7 表示一个二叉树
     * 输出格式：[[3], [9, 20], [15, 7]]，每个子列表表示一层的节点值
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取二叉树节点值
        String[] nodes = sc.nextLine().split(" ");
        
        // 构建二叉树并进行层序遍历
        TreeNode root = buildTree(nodes);
        System.out.println(levelOrderM(root));
        sc.close();
    }
}
